﻿/*
 * Malte Frerichs
 * Melvin Bos
 * Jasper ter Weeme
 */

using System;
using System.Collections.Generic;

namespace SortOf
{

    public class MergeSort : ISort
    {
        private void Merge<T>(IList<T> numbers, int left, int mid, int right) where T : IComparable<T>
        {
            T[] temp = new T[25];
            int i, left_end, num_elements, tmp_pos;
            left_end = (mid - 1);
            tmp_pos = left;
            num_elements = (right - left + 1);

            // vergelijk de paren
            while ((left <= left_end) && (mid <= right))
            {
                if (numbers[left].CompareTo(numbers[mid]) <= 0)
                {
                    temp[tmp_pos++] = numbers[left++];
                }
                else
                {
                    temp[tmp_pos++] = numbers[mid++];
                }
            }

            // linkerhelft
            while (left <= left_end)
            {
                temp[tmp_pos++] = numbers[left++];
            }

            // rechterhelft
            while (mid <= right)
            {
                temp[tmp_pos++] = numbers[mid++];
            }


            for (i = 0; i < num_elements; i++)
            {
                numbers[right] = temp[right];
                right--;
            }
        }

        private void Sort<T>(IList<T> list, int left, int right) where T : IComparable<T>
		{
            int mid;

            // als rechts groter is, dan is het sorteren nog niet klaar
            if (right > left)
            {
                mid = (right + left) / 2;

                // sort is recursief
                Sort(list, left, mid);
                Sort(list, mid + 1, right);

                // voeg twee paren samen
                Merge(list, left, mid + 1, right);
            }
		}



		public void Apply<T>(IList<T> list) where T : IComparable<T>
		{
			Sort(list, 0, list.Count - 1);
		}
	}
}
